#include <iostream>
#include <vector>
using namespace std;

int Partition(vector<int> &vec, int low, int high)
{
    int i = low, j = high;
    int tmp = vec[low];

    while (i < j)
    {
        while (i < j && vec[j] >= tmp)
            j--;
        vec[i] = vec[j];
        while (j > i && vec[i] <= tmp)
            i++;
        vec[j] = vec[i];
    }
    vec[i] = tmp;
    return i;
}

vector<vector<int>> Solution(vector<int> vec)
{
    int vec_size = vec.size();
    int low = 0, high = vec_size - 1;
    int i = 0;
    while (i != vec_size / 2 - 1)
    {
        i = Partition(vec, low, high);
        if (vec_size / 2 - 1 > i)
            low = i + 1;
        else if (vec_size / 2 - 1 < i)
            high = i - 1;
    }

    vector<int> s1, s2;
    for (i = 0; i < vec_size / 2; i++)
        s1.push_back(vec[i]);
    for (i; i < vec_size; i++)
        s2.push_back(vec[i]);

    return vector<vector<int>>{s1, s2};
}

int main()
{
    vector<int> nums{1, 8, 5, 3, 4, 2, 9, 6, 7, 0};
    auto result = Solution(nums);

    for (vector<int> arr : result)
    {
        for (int num : arr)
            cout << num << " ";
        cout << endl;
    }

    return 0;
}